/*
 * stable_matcher_impl.h
 *
 *  Created on: May 1, 2011
 *      Author: tqlong
 */

#ifndef STABLE_MATCHER_IMPL_H_
#define STABLE_MATCHER_IMPL_H_
#include "stable_matcher.h"

template <typename D1, typename D2>
StableMatcher<D1, D2>::StableMatcher(dataset1_type& data1, dataset2_type& data2, double r, double norm) :
  __Base(data1, data2), m_r(r), m_norm(norm)
{
  m_tree = new tree1_type(data1);
  m_tree->buildTree();
}

template <typename D1, typename D2>
void StableMatcher<D1,D2>::doMatch()
{
  computeRange();

  int nn = this->m_data1.n() + this->m_data2.n();
  int n1 = this->m_data1.n();
  int n2 = this->m_data2.n();
  m_matchIdx  = vint_type(nn, -1);
  m_matchDist = vdouble_type(nn, 0);
  m_currentPos  = vint_type(this->m_data2.n(), 0);

  std::queue<int> freeBid;
  for (int i = 0; i < n2; i++) freeBid.push(i);

  while (!freeBid.empty())
    {
      int m = freeBid.front();
      freeBid.pop();
      int pos = m_currentPos[m];
      if (pos < m_range[m].size())
        {
          m_currentPos[m]++; // next time try the next candidate
          int w = m_range[m][pos].idx; // get the women index
          double d = m_range[m][pos].dist; // and the distance
          int m_prime = m_matchIdx[w + n2]; // get the current man engage to that woman

          if (m_prime == -1)  // the women is not engaged
            {
              match(m, w, d);
            }
          else if (d < m_matchDist[m_prime])
            {
              m_matchIdx[m_prime] = -1; // remove engagement status of that man
              freeBid.push(m_prime); // and put him back in the queue
              match(m, w, d);
            }
        }
    }
}

template <typename D1, typename D2>
void StableMatcher<D1,D2>::computeRange()
{
  for (int j = 0; j < this->m_data2.n(); j++)
    {
      visitor1_type v(this->m_data2.get(j), m_r, true, m_norm);
      searchTree<tree1_type, visitor1_type>(m_tree, v);

      m_range.push_back(ventry_type());
      ventry_type& vent = m_range.back();
      for (unsigned int k = 0; k < v.m_idx.size(); k++)
        {
          vent.push_back(entry_type());
          vent.back().idx = m_tree->origIdx(v.m_idx[k]);
          vent.back().dist = v.m_dist[k];
        }
      std::sort(vent.begin(), vent.end(), less_entry());
    }
}

template <typename D1, typename D2>
void StableMatcher<D1,D2>::match(int m, int w, double dist)
{
  int n2 = this->m_data2.n();
  m_matchIdx[m] = w+n2;
  m_matchIdx[w+n2] = m;
  m_matchDist[m] = dist;
  m_matchDist[w+n2] = dist;
}

#endif /* STABLE_MATCHER_IMPL_H_ */
